#include <bits/stdc++.h>

using namespace std;

// 利用先序与中序遍历序列构造二叉树
// 测试链接 : https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 提交如下的方法
class Solution 
{
public:
    TreeNode* f(vector<int>& pre, int l1, int r1, vector<int>& in, int l2, int r2, unordered_map<int, int>& m)
    {
        if(l1 > r1) return nullptr;
        
        TreeNode* root = new TreeNode(pre[l1]);
        if(l1 == r1) return root;
        int k = m[pre[l1]];
        // pre : l1(........)[.......r1]
		// in  : (l2......)k[........r2]
		// (...)是左树对应，[...]是右树的对应
        root->left = f(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, m);
        root->right = f(pre, r1 + k + 1 - r2, r1, in, k + 1, r2, m);
        return root;
    }

    TreeNode* buildTree(vector<int>& pre, vector<int>& in) 
    {
        if(pre.empty() || in.empty() || pre.size() != in.size()) return nullptr;
        unordered_map<int, int> m;
        int n = in.size();
        for(int i = 0; i < n; ++i) m[in[i]] = i;
        return f(pre, 0, n - 1, in, 0, n - 1, m);
    }
};


// 另一种写法
class Solution 
{
private:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder, int& preI, int inBegin, int inEnd)
    {
        if(inBegin > inEnd)
            return nullptr;
        
        // 构建根
        TreeNode* root = new TreeNode(preorder[preI]);
        // 用中序结果来分割左右子树
        int inI = inBegin;
        while(inI <= inEnd)
        {
            if(inorder[inI] == root->val)
                break;
            else
                ++inI;
        }

        // [inBegin, inI - 1] inI [inI + 1, inEnd]
        // 构建左子树和右子树
        ++preI; // 找出左右子树的根
        root->left = _buildTree(preorder, inorder, preI, inBegin, inI - 1);
        root->right = _buildTree(preorder, inorder, preI, inI + 1, inEnd);
        return root;
    }
public:


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) 
    {
        int i = 0;
        return _buildTree(preorder, inorder, i, 0, inorder.size() - 1);
    }
};